#include <unordered_map>
/*
class Solution {
public:
    int numWays(int n) {
        if(n==0||n==1)
            return 1;
        vector<int> dp(n+1,1);
        int i;
        for(i = 2;i<=n;i++)  // 迭代方式
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n]%1000000007;
    }
};*/
class Solution {
 public:
  std::unordered_map<int, int>
      mp;  // 记忆化递归，否则栈溢出,千万注意是否会爆栈！！！
  int func(int n) {
    if (n == 0 || n == 1) return 1;
    if (mp.count(n))
      return mp[n];
    else {
      mp[n - 1] =
          func(n - 1) %
          1000000007;  // 想成mp[n-1]即跳到n-1梯的跳法已经计算完成，把递归调用当成一个表达式
      mp[n - 2] = func(n - 2) % 1000000007;
      mp[n] = (mp[n - 1] + mp[n - 2]) % 1000000007;
    }
    return mp[n];
  }
  int numWays(int n) { return func(n); }
};

// 递归三部曲：
// 1. 确定递归函数功能，设计递归函数签名：传入整数n，返回跳到n的所有跳法
// 2. 确定递归终止条件：n==0||n==1
// 3. 完成单层递归：从哪里跳到第n梯